package org.kk.tree;
import org.kk.Common.TreeNode;

import java.util.ArrayList;
import java.util.List;

/**
 * 路径总和
 * @author kk
 * @Date 2021/2/7
 */
public class PathSum {
    public static void main(String[] args) {
        int[] nums = {6,5,2,3,1,3,4,5};
        TreeNode treeNode = sortedArrayToBST(nums, 0, nums.length - 1);
        List<Integer> result = new ArrayList<>();
        print(treeNode, result);
        System.out.println(result);
        int i = pathSum(treeNode, 5);
        System.out.println(i);
    }
    public static void print(TreeNode root, List<Integer> list){
        if(root != null){
            print(root.left,list);
            list.add(root.val);
            print(root.right, list);
        }
    }
    public static TreeNode sortedArrayToBST(int[] nums, int left, int right){
        if(left > right) return null;
        int mid = (left + right) >>> 1;
        TreeNode root = new TreeNode(nums[mid]);
        root.left = sortedArrayToBST(nums, left, mid -1);
        root.right = sortedArrayToBST(nums, mid + 1, right);
        return root;
    }
    public static int pathSum(TreeNode root, int sum){
        if(root == null) return 0;
        return count(root, sum) + pathSum(root.left, sum) + pathSum(root.right, sum);
    }
    private static int count(TreeNode root, int sum){
        if(root == null) return 0;
        if(root.val == sum) return 1;
        return count(root.left, sum - root.val) + count(root.right, sum - root.val);
    }
}
